/* ANSWER
 * Use backtracking and recursion.
 * We need a stack to help backtracking the path.
 */
#include <stdio.h>
#include <stdlib.h>
#include "pathvalue.h"

#define MAX_HEIGHT  10

void btree_init(struct TreeNode **root) {
  struct TreeNode *ptr = NULL;
  ptr = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  *root = ptr;
  ptr->data = 10;
    ptr->left = NULL;
  ptr->right = NULL;

  ptr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  ptr->left->data = 5;
  ptr->left->left = NULL;
  ptr->left->right = NULL;

  ptr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  ptr->right->data = 12;
  ptr->right->left = NULL;
  ptr->right->right = NULL;

  ptr = ptr->left;
  
  ptr->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  ptr->left->data = 4;
  ptr->left->left = NULL;
  ptr->left->right = NULL;

  ptr->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  ptr->right->data = 7;
  ptr->right->left = NULL;
  ptr->right->right = NULL;

  return;
}

void print_path(int path[], int top) {
  int i;
  for (i = 0; i < top; i++)
    printf("%d ", path[i]);
  printf("\n");

  return;
}

void find_path(struct TreeNode *root, int sum, int path[], int top) {
  path[top++] = root->data;
  sum -= root->data;
  if (NULL == root->left && NULL == root->right) {
    /* 如果当前结点为叶结点，并且当前路径的和刚好等于输入的整数 */
    /* 符合要求，打印路径 */
    if (sum == 0) print_path(path, top);
  } else {
    if (root->left != NULL)
      find_path(root->left, sum, path, top);

    if (root->right != NULL)
      find_path(root->right, sum, path, top);
  }

  /* 函数返回前，在路径上删除当前结点的值，以确保返回父结点时， */
  /* 路径刚好是根结点到父结点的路径 */
  top --;
  sum += root->data;

  return;
}

void print_paths(struct TreeNode *root, int sum) {
  int path[MAX_HEIGHT];
  find_path(root, sum, path, 0);
  
  return;
}

int main(int argc, char *argv[]) {
  struct TreeNode *root = NULL;
  btree_init(&root);
  print_paths(root, 22);
  return 0;
}
